ABC125 C - GCD on Blackboard
https://atcoder.jp/contests/abc125/tasks/abc125_c
提出
TLE
code: python
from functools import reduce
import math
n = int(input())
a = list(map(int, input().split()))
def my_gcd(numbers):
return reduce(math.gcd, numbers)
ans = -1
for i in range(n):
res = my_gcd(a:i + ai+1:)
if (res > ans):
ans = res
print(ans)
解答
code: python
import math
n = int(input())
a = list(map(int, input().split()))
left = 0 * (n + 1)
for i in range(n):
lefti+1 = math.gcd(lefti, ai)
right = 0 * (n + 1)
for i in range(n-1, -1, -1):
righti = math.gcd(righti+1, ai)
# 3
# 12 15 18
# print(left, right)
# 0, 12, 3, 3 3, 3, 18, 0
res = 0
for i in range(n):
l = lefti
r = righti+1
gcd_val = math.gcd(l, r)
if gcd_val > res:
res = gcd_val
print(res)
テーマ
#gcd #cumulativeSum
メモ
AtCoder abc125_c GCD on Blackboard
提出
code: python
import functools
import math
n = int(input())
a = list(map(int, input().split()))
ans = -1
for i in range(n):
res = functools.reduce(math.gcd, a:i + ai+1:)
if res > ans:
ans = res
print(ans)